// https://www.lintcode.com/problem/coins-in-a-line-iii/my-submissions

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        int n = values.size();
        if (n == 0)
            return true;
        vector<vector<int>> res(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
        {
            res[i][i] = values[i];
        }
        for (int len = 2; len <= n; ++len)
        {
            for (int i = 0; i <= n - len; ++i)
            {
                int j = i + len - 1;
                res[i][j] = max(values[i] - res[i + 1][j], values[j] - res[i][j - 1]);
            }
        }
        return res[0][n - 1] >= 0;
    }
};